package lc.q51_100;

/**
 * 给定三个字符串 s1, s2, s3, 验证 s3 是否是由 s1 和 s2 交错组成的。
 */
public class Q97 {
    public boolean isInterleave(String s1, String s2, String s3) {
        // 将两段字符串得交错形式组合起来
//        return isInterleave(s1, 0, s2, 0, "", s3);
        return dfs(s1, s2, s3);
    }

    // 二维动态规划
    private boolean dfs(String s1, String s2, String s3) {
        if (s1.length() + s2.length() != s3.length()) {
            return false;
        }
        // s3的前缀应该能够被s1的前缀和s2的前缀形成
        // 这里就用一个二维数组来包含所有的s1的前缀和s2的前缀，i表示s1的前i项，j表示s2的前j项,（i+j）表示s3的前(i+j）项
        boolean[][] dp = new boolean[s1.length()+1][s2.length()+1];
        dp[0][0] = true;
        // n = 分解
        for (int i = 0; i <= s1.length(); i++) {
            for (int j = 0; j <= s2.length(); j++) {

                if (i==0&&j==0) {
                    continue;
                }
                if (j != 0) {
                    dp[i][j] |= (s3.charAt(i+j-1) == s2.charAt(j-1) && dp[i][j-1]);
                }
                if (i != 0) {
                    dp[i][j] |= (s3.charAt(i+j-1) == s1.charAt(i-1) && dp[i-1][j]);
                }

            }
        }
        return dp[s1.length()][s2.length()];
    }

    private boolean isInterleave(String s1, int i, String s2, int j, String res, String s3) {
        // 如果i和j都到头了
        // 回溯算法
        if (res.equals(s3) && i == s1.length() && j == s2.length()) {
            return true;
        }
        boolean ans = false;
        if (i < s1.length()) {
            ans |= isInterleave(s1, i +1, s2, j, res+s1.charAt(i), s3);
        }
        if (j < s2.length()) {
            ans |= isInterleave(s1, i, s2, j+1, res+s1.charAt(i), s3);
        }
        return ans;
    }

    public static void main(String[] args) {
        Q97 q97 = new Q97();
        System.out.println(q97.isInterleave("aabcc","dbbca", "aadbbcbcac"));
    }

}
